package lc.Q200_250;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [3,2,3]
 * 输出：[3]
 * 示例 2：
 *
 * 输入：nums = [1]
 * 输出：[1]
 * 示例 3：
 *
 * 输入：nums = [1,2]
 * 输出：[1,2]
 */
public class Q229 {

    public static void main(String[] args) {
        Q229 q229 = new Q229();
        System.out.println(q229.majorityElement2(new int[]{
                2,2
        }));
    }
    public List<Integer> majorityElement2(int[] nums) {
        // 摩尔投票法
        int ele1 = 0;
        int ele2 = 0;
        int vote1 = 0;
        int vote2 = 0;
        for (int num : nums) {
            // 如果候选人1投票>0并且当前数等于候选1
            if (vote1 > 0 && num == ele1) {
                vote1 ++;
            }
            else if (vote2 > 0 && num == ele2) {
                vote2 ++;
            }
            else if (vote1 == 0) {
                ele1 = num;
                vote1 ++;
            }
            else if (vote2 == 0) {
                ele2 = num;
                vote2 ++;
            } else {
                vote1 --;
                vote2 --;
            }
        }
        // 投票完成，计数
        int cnt1 =0, cnt2 = 0;
        for (int num : nums) {
            if (vote1> 0 && num == ele1) {
                cnt1 ++;
            }
            else if (vote2 > 0 &&num == ele2) {
                cnt2 ++;
            }
        }
        List<Integer> result = new ArrayList<>();
        if (vote1 > 0 && cnt1 > nums.length / 3) {
            result.add(ele1);
        }
        if (vote2 > 0 && cnt2 > nums.length / 3) {
            result.add(ele2);
        }
        return result;
    }

    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<>();
        // 计数
        Map<Integer, Integer> counter = new HashMap<>();
        int count = nums.length / 3;
        for (int num : nums) {
            Integer orDefault = counter.getOrDefault(num, 0);
            counter.put(num, orDefault + 1);
            if (orDefault == count) {
                result.add(num);
            }
        }
        // todo 优化：采用摩尔投票法，两个候选人，
        return result;
    }
}
